class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;   // 统计前缀和出现的次数
        hash[0 % k] = 1;    // 0 这个数的余数

        int sum = 0, ret = 0;
        for(auto& e : nums)
        {
            sum += e;   // 计算当前位置的前缀和
            int tmp = (sum % k + k) % k;    // 修正后的余数
            if(hash.count(tmp))
                ret += hash[tmp];   // 统计个数
            hash[tmp]++;
        }
        return ret;
    }
};